package dynamicprograming

// fibonacci is a function that returns the nth number in the fibonacci sequence
func fibonacci(n int) int {
	if n <= 1 {
		return n
	}
	return fibonacci(n-1) + fibonacci(n-2)
}

func climbStairs(n int) [][]int {
	type Steps [][]int
	var climbStairsHelper func(n int) Steps
	climbStairsHelper = func(n int) Steps {
		if n <= 1 {
			return Steps{[]int{n}}
		}
		dp := make([]Steps, n+1)
		dp[0] = Steps{[]int{}}
		dp[1] = Steps{[]int{1}}
		dp[2] = Steps{[]int{1, 1}, []int{2}}
		for i := 3; i <= n; i++ {
			for _, step := range dp[i-1] {
				dp[i] = append(dp[i], append(step, 1))
			}
			for _, step := range dp[i-2] {
				dp[i] = append(dp[i], append(step, 2))
			}
		}
		return dp[n]
	}
	return climbStairsHelper(n)
}
